The present invention relates to a circuit for the fast calculation of the direct cosine transform of a discrete signal and a circuit for the fast calculation of the inverse cosine transform of a discrete signal. These transforms are more particularly used in the processing of signals of digital images or pictures and particularly for the coding and decoding of high resolution images or pictures. The invention relates to the reverse or direct discrete cosine transforms in which the signal to be processed is represented by N points, N being in the form 2.sup.n, in which n is an integer.
In general terms, the cosine transform of a sequence (x.sub.i),0.ltoreq.i.ltoreq.N-1, representing the discretized signal to be processed in a sequence (X.sub.i),0.ltoreq.i.ltoreq.N-1 is obtained by a sequence of operators, each operator receiving from the preceding operator a group of N points and supplying to the following operator a sequence of N points obtained from the points received at the input by simple mathematical operations. These mathematical operations are essentially additions and multiplications, to which a permutation may optionally be added.
In the present invention, the cosine transform calculating circuit comprises a sequence of stages, each stage realising an operator and leading to the appearance of N intermediate numbers, each being a linear combination of at the most two numbers from the preceding stage. Each operator can be mathematically represented by a matrix of size N.times.N. The cosine transform circuit is then defined by a product of matrixes. In the case where said matrixes are orthogonal, they are easily invertible. Thus, their inverse is equal, optionally to within a multiplication factor, to their transpose. The inverse cosine transform circuit is then defined by the product of the transposed matrixes, taken in the reverse order of that of the product of the matrixes of the direct transform.
In the circuit according to the invention, the matrixes of the direct transform are not orthogonal. However, the product of each matrix by its transpose is a diagonal matrix and it is found that the inverse transform is defined by the product of said transposed matrixes, performed in the reverse order of the product of the matrixes of the direct transform, multiplied by a coefficient equal to (2/N). The circuit of the reverse transform is thus simply obtained by reversing the order of the stages of the direct transform circuit, the coefficient (2/N) being either included in one of the multiplier stages of the direct transform or is obtained by means of a supplementary multiplier stage.
An adder stage of form a.+-.b defines the value of an output point as the sum or difference of the values of two input points. A multiplier stage of form .alpha..a.+-..beta..b associates with each output point the sum or difference of the value of two input points allocated with predetermined coefficients .alpha. and .beta.. This stage can be provided with means for exchanging the coefficients .alpha. and .beta., so as to produce .alpha.a.+-..beta.b or .beta.a.+-..alpha.b
The operator of one stage may not apply to all the input points. The value of certain output points is then simply equal to the value of one input point or to its opposite. Such an operator is said to have a transparent state. Texas Instruments circuit 74181 is an example of an adder-subtracter with a transparent state.
At a practical level, an adder stage comprises at least one adder-subtracter. A multiplier stage is more complex, because it requires at least one multiplier with accumulator or a multiplier with an adder-subtracter. These circuits must be fast for the real time processing of image signals, such as video signals and these circuits are onerous.
The number of adders-substracters and multipliers in a circuit for the fast calculation of the cosine transform is consequently a particularly important criterion in the field of the invention. It should also be noted that the cost of a multiplier is much higher than the cost of an adder and that the reduction in the number of multiplier stages in the circuit is particularly desired.
The article "A fast computational algorithm for the discrete cosine transform" by W. H. CHEN, which appeared in IEEE Transactions on Communications, Vol 25, No 9, September 1977, pp 1004 to 1009 discloses a process for the fast calculation of the cosine transform. In this article, the process for the fast calculation of the cosine transform is defined by a matrix [A.sub.N ] equal to a product of matrixes of size N.times.N. Each matrix represents an operator and corresponds to one stage of the circuit. The matrix [A.sub.N ] is equal to: ##EQU1## in which [P.sub.N ] is a permutation matrix N.times.N, the block [A.sub.N/2 ] is the matrix corresponding to the cosine transform of a group of N/2 points, the block [R.sub.N/2 ] is a product of 2n-3 matrixes, in which n=log.sub.2 N and [B.sub.N ] is a matrix, whose terms located on the two diagonals are equal to .+-.1, the other terms being zero.
The 2n-3 matrixes are broken down into n-1 multiplier matrixes and n-2 adder matrixes. The adder matrixes are those in which the non-zero coefficients are equal to .+-.1. The multiplier matrixes have sine or cosine terms. The cosine transform circuit described in this article thus comprises n-1 multiplier stages and n-1 adder stages, whilst taking account of the stage corresponding to the matrix [B.sub.N ]. Account is not taken of the stage or the permutation matrix P.sub.N, which does not constitute a real calculation.
The known circuit for the fast calculation of the cosine transform described hereinbefore has been slightly modified to permit pipeline processing. These modifications essentially comprise delaying by one or more stages the calculation performed on certain points of the group of N processed points and of providing operators with four inputs. This permits the parallel operation of all the stages of the circuit performing the process.
Reference should be made to the article "A high speed FDCT processor for real-time processing of NTSC colour TV signal", By A. JALALI and K. R. RAO, which appeared in IEEE Transactions on Electromagnetic Compatibility, Vol 24, No 2, May 1982, pp 278 to 286 for a more detailed description of this circuit.